package com.gitee.wsl.collections.map

import com.gitee.wsl.ext.base.Arrays.arraycopy
import com.gitee.wsl.func.consumer.BiConsumer
import com.gitee.wsl.func.consumer.Consumer


/**
 * Implements a radix array mapped trie data structure, with radix=32
 *
 *
 *
 * The key is a primitive <tt>int</tt> and allows all range of integer values.
 *
 *
 *
 * The data structure is optimal when keys are grouped around a limited range of
 * values with low dispersion. The map is designed to store values associated to
 * a set of bounded int keys.
 *
 *
 *
 * Can be used as a map with integers as key (`Map<Integer, T>`) or a
 * compact unbounded integer array (Integer[T])
 *
 *
 *
 * The implementation uses a Radix tree over int keys. Each node of the trie has
 * 5 bits.
 *
 *
 *
 * Iteration over its elements is done in preorder and it is sorted in ascending
 * order.
 *
 * @param <V>
 * Type of the associated element
</V> */
//class RadixTrie<V>() : IntKeyMap<V>{
//    private var root: RadixTrieNode? = null
//    private var size = 0
//
//    /**
//     * Constructs a new `RadixTrie` with the same mappings as the specified
//     * `IntKeyMap`.
//     *
//     * @param m
//     * the map whose mappings are to be placed in this map
//     * @throws NullPointerException
//     * if the specified map is null
//     */
//    constructor(m: IntKeyMap<V>) : this() {
//        putAll(m)
//    }
//
//    public override fun put(key: Int, value: V): V? {
//        if (root == null) {
//            root = newLeafNode(key, value)
//            return incSize()
//        }
//        var previousNode: RadixTrieNode? = null
//        var previousIndex = 0
//        var currentNode = root
//        while (true) {
//            val numberNonPrefixBits = currentNode!!.numberNonPrefixBits + BIT_SIZE
//            val currentNodePrefixBits = currentNode.prefixBits
//            val keyPrefixBits = getKeyPrefixBits(key, numberNonPrefixBits)
//            if (keyPrefixBits != currentNodePrefixBits) {
//                val numberOfBitsInXor = nonPrefixBitsSharedInXor(keyPrefixBits xor currentNodePrefixBits)
//                val parentNode = currentNode.createParentNodeWith(key, value, numberOfBitsInXor)
//                if (previousNode == null) {
//                    root = parentNode
//                } else {
//                    previousNode.set(previousIndex, parentNode)
//                }
//                return incSize()
//            }
//            if (isLeafNode(numberNonPrefixBits)) {
//                return incSize(currentNode.set(key and BIT_MASK, value) as V?)
//            }
//            val idx = getIdxInNode(key, numberNonPrefixBits)
//            val nextNode = currentNode.get(idx) as RadixTrieNode?
//            if (nextNode == null) {
//                currentNode.set(idx, newLeafNode(key, value))
//                return incSize()
//            }
//            previousNode = currentNode
//            previousIndex = idx
//            currentNode = nextNode
//        }
//    }
//
//    private fun incSize(): V? {
//        size++
//        return null
//    }
//
//    private fun incSize(previousValue: V?): V? {
//        if (previousValue == null) {
//            size++
//        }
//        return previousValue
//    }
//
//    public override fun get(key: Int): V? {
//        var currentNode = root
//        while (currentNode != null) {
//            val numberNonPrefixBits = currentNode.numberNonPrefixBits + BIT_SIZE
//            if (getKeyPrefixBits(key, numberNonPrefixBits) != currentNode.prefixBits) {
//                return null
//            }
//            if (isLeafNode(numberNonPrefixBits)) {
//                return currentNode.get(key and BIT_MASK) as V?
//            }
//            currentNode = currentNode.get(getIdxInNode(key, numberNonPrefixBits)) as RadixTrieNode?
//        }
//        return null
//    }
//
//    public fun remove(key: Int): V? {
//        if (root == null) {
//            return null
//        }
//        val removed = remove(root!!, key)
//        if (removed != null) {
//            if (root!!.isEmpty) {
//                root = null
//            }
//            size--
//        }
//        return removed
//    }
//
//    private fun remove(currentNode: RadixTrieNode, key: Int): V? {
//        val numberNonPrefixBits = currentNode.numberNonPrefixBits + BIT_SIZE
//        if (getKeyPrefixBits(key, numberNonPrefixBits) != currentNode.prefixBits) {
//            return null
//        }
//        if (isLeafNode(numberNonPrefixBits)) {
//            return currentNode.remove(key and BIT_MASK) as V?
//        }
//        val idxInNode = getIdxInNode(key, numberNonPrefixBits)
//        val nextNode = currentNode.get(idxInNode) as RadixTrieNode?
//        if (nextNode == null) {
//            return null
//        }
//        val removed = remove(nextNode, key)
//        if (removed != null) {
//            if (nextNode.isEmpty) {
//                currentNode.remove(idxInNode)
//            }
//            // TODO: if size is 1 and is not leaf collapse it
//        }
//        return removed
//    }
//
//    public  fun forEachKey(action: Consumer<Int>) {
//
//        forEachKey(root!!, action)
//    }
//
//    public override fun containsValue(value: V): Boolean {
//        return Companion.containsValue(root!!, value)
//    }
//
//
//
//    fun clear() {
//        root = null
//        size = 0
//    }
//
//    /**
//     * Returns a shallow copy of this <tt>RadixTrie</tt> instance: the elements
//     * themselves are not cloned.
//     *
//     * @return a shallow copy of this map
//     */
////    public override fun clone(): Any {
////        try {
////            val newMap = super.clone() as RadixTrie<V?>
////            forEach(Consumer { key: Int, value: V? -> newMap.put(key, value) })
////            return newMap
////        } catch (e: CloneNotSupportedException) {
////            throw InternalError(e)
////        }
////    }
//
//    public  fun forEach(action: BiConsumer<Int, V>) {
//        forEach(root!!, action)
//    }
//
//    private fun forEach(node: RadixTrieNode, action: BiConsumer<Int, V>) {
//        if (node.isLeaf) {
//            node.forEach{ idx, value -> action.accept(idx, value as V) }
//        } else {
//            node.forEachValue(Consumer { value: Any? -> forEach((value as RadixTrie.RadixTrieNode?)!!, action) })
//        }
//    }
//
//    public  fun forEach(action: Consumer<in BiConsumer<Int, V>>) {
//        forEach({ i, t -> action.accept(IntObjectEntry(i, t)) })
//    }
//
//      fun iterator(): Iterator<IntObjectEntry<V?>?> {
//        if (isEmpty()) {
//            return emptyIterator()
//        }
//        return RadixTrie.EntryIterator()
//    }
//
////    public override fun spliterator(): Spliterator<IntObjectEntry<V?>?> {
////        return Spliterators.spliterator(
////            this.iterator(), this.size,
////            Spliterator.DISTINCT + Spliterator.NONNULL + Spliterator.SIZED
////        )
////    }
//
//    public  fun values(): Collection<V> {
//        return RadixTrie.Values()
//    }
//
//    public  fun keySet(): Set<Int> {
//        return RadixTrie.KeySet()
//    }
//
//    public  fun entrySet(): Set<IntObjectEntry<V>>? {
//        return RadixTrie.EntrySet()
//    }
//
//    /**
//     * Abstract implementation like `Iterator<IntObjectEntry<T>>` which is
//     * extended later by [EntryIterator] [ValueIterator] and
//     * [KeyIterator].
//     */
//    private abstract inner class IntIterator {
//        private var currentLeaf: IteratorLevel? = null
//
//        init {
//            val rootLevel: IteratorLevel = RadixTrie.IntIterator.IteratorLevel(root, null)
//            currentLeaf = rootLevel.fillStack()
//        }
//
//        fun hasNextIt(): Boolean {
//            return currentLeaf != null && currentLeaf.hasNext()
//        }
//
//        fun nextIt(): IntObjectEntry<V?> {
//            if (!hasNextIt()) {
//                throw NoSuchElementException()
//            }
//            val res: IntObjectEntry<V?> = currentLeaf.getNextValue()
//            if (!currentLeaf.hasNext()) {
//                currentLeaf = popAndFillStackToNext()
//            }
//            return res
//        }
//
//        fun popAndFillStackToNext(): IteratorLevel? {
//            currentLeaf = currentLeaf.parent
//            if (currentLeaf == null) {
//                return null
//            }
//            if (currentLeaf.hasNext()) {
//                return currentLeaf.fillStackFromLevel()
//            }
//            return popAndFillStackToNext()
//        }
//
//        private inner class IteratorLevel(node: RadixTrieNode, private val parent: IteratorLevel?) {
//            private val childNodeIterator: Iterator<IntObjectEntry<*>?> = node.iterator()
//            private val isLeaf: Boolean = node.isLeaf
//
//            fun fillStackFromLevel(): IteratorLevel? {
//                val nextChild: IntObjectEntry<*> = childNodeIterator.next()
//                val childNode = nextChild.getValue() as RadixTrieNode
//                val lowerLevel: IteratorLevel = RadixTrie.IntIterator.IteratorLevel(childNode, this)
//                return lowerLevel.fillStack()
//            }
//
//            fun fillStack(): IteratorLevel? {
//                return if (isLeaf) this else fillStackFromLevel()
//            }
//
//            val nextValue: IntObjectEntry<V?>
//                get() {
//                    val nextChild = childNodeIterator.next()
//                    return IntObjectEntry(nextChild.key, nextChild.value as V?)
//                }
//
//            fun hasNext(): Boolean {
//                return childNodeIterator.hasNext()
//            }
//        }
//    }
//
//    private inner class Values : AbstractCollection<V?>() {
//        public override fun size(): Int {
//            return this@RadixTrie.size()
//        }
//
//        public override fun clear() {
//            this@RadixTrie.clear()
//        }
//
//        public override fun iterator(): Iterator<V?>? {
//            if (isEmpty()) {
//                return emptyIterator()
//            }
//            return RadixTrie.ValueIterator()
//        }
//
//        public override fun contains(o: Any?): Boolean {
//            return containsValue(o)
//        }
//
////        public override fun spliterator(): Spliterator<V?> {
////            return Spliterators.spliterator(this.iterator(), size, Spliterator.NONNULL + Spliterator.SIZED)
////        }
//
//        public override fun forEach(action: Consumer<in V?>) {
//            requireNonNull(action)
//            this@RadixTrie.forEach({ key, value -> action.accept(value) })
//        }
//    }
//
//    private inner class KeySet : AbstractSet<Int?>() {
//        public override fun size(): Int {
//            return this@RadixTrie.size()
//        }
//
//        public override fun clear() {
//            this@RadixTrie.clear()
//        }
//
//        public override fun iterator(): Iterator<Int?>? {
//            if (isEmpty()) {
//                return emptyIterator()
//            }
//            return RadixTrie.KeyIterator()
//        }
//
//        public override fun contains(o: Any?): Boolean {
//            return containsKey(o as Int?)
//        }
//
//        public override fun spliterator(): Spliterator<Int?> {
//            return Spliterators.spliterator(this.iterator(), size, Spliterator.NONNULL + Spliterator.SIZED)
//        }
//
//        public override fun forEach(action: Consumer<in Int?>) {
//            requireNonNull(action)
//            this@RadixTrie.forEachKey(IntConsumer { key -> action.accept(key) })
//        }
//    }
//
//    private inner class EntrySet : AbstractSet<IntObjectEntry<V?>?>() {
//        public override fun size(): Int {
//            return this@RadixTrie.size()
//        }
//
//        public override fun clear() {
//            this@RadixTrie.clear()
//        }
//
//        public override fun iterator(): Iterator<IntObjectEntry<V?>?>? {
//            if (isEmpty()) {
//                return emptyIterator()
//            }
//            return RadixTrie.EntryIterator()
//        }
//
//        public override fun contains(o: Any?): Boolean {
//            requireNonNull(o, "Value can not be null")
//            val key: IntObjectEntry<V?> = o as IntObjectEntry<V?>
//            val value = get(key.getIntKey())
//            return (value != null && value == key.getValue())
//        }
//
//        public override fun spliterator(): Spliterator<IntObjectEntry<V?>?> {
//            return Spliterators.spliterator(this.iterator(), size, Spliterator.NONNULL + Spliterator.SIZED)
//        }
//
//        public override fun forEach(action: Consumer<in IntObjectEntry<V?>?>) {
//            requireNonNull(action)
//            this@RadixTrie.forEach(action)
//        }
//    }
//
//    private inner class EntryIterator : IntIterator(), Iterator<IntObjectEntry<V?>?> {
//        public override fun hasNext(): Boolean {
//            return hasNextIt()
//        }
//
//        public override fun next(): IntObjectEntry<V?> {
//            return nextIt()
//        }
//    }
//
//    private inner class ValueIterator : IntIterator(), Iterator<V?> {
//        public override fun hasNext(): Boolean {
//            return hasNextIt()
//        }
//
//        public override fun next(): V? {
//            return nextIt().getValue()
//        }
//    }
//
//    private inner class KeyIterator : IntIterator(), Iterator<Int?> {
//        public override fun hasNext(): Boolean {
//            return hasNextIt()
//        }
//
//        public override fun next(): Int {
//            return nextIt().getIntKey()
//        }
//    }
//
//    override fun equals(o: Any?): Boolean {
//        if (o === this) {
//            return true
//        }
//        if (o !is IntKeyMap) {
//            return false
//        }
//        val m = o as IntKeyMap<*>
//        if (m.size() !== size()) {
//            return false
//        }
//        try {
//            // TODO: implements traversing both trees in parallel if RadixTrie
//            for (e in entrySet()!!) {
//                val key: Int = e.getIntKey()
//                val value: V? = e.getValue()
//                if (value != m.get(key)) {
//                    return false
//                }
//            }
//        } catch (unused: ClassCastException) {
//            return false
//        } catch (unused: NullPointerException) {
//            return false
//        }
//        return true
//    }
//
//    override fun hashCode(): Int {
//        var hash = 0
//        val it: Iterator<IntObjectEntry<V?>?> = iterator()
//        while (it.hasNext()) {
//            hash += it.next().hashCode()
//        }
//        return hash
//    }
//
//    override fun toString(): String {
//        val i: Iterator<IntObjectEntry<V?>?> = iterator()
//        if (!i.hasNext()) {
//            return "{}"
//        }
//        val sb: StringBuilder = StringBuilder()
//        sb.append('{')
//        while (true) {
//            val e: IntObjectEntry<V?> = i.next()
//            sb.append(e.getIntKey())
//            sb.append('=')
//            val value: V? = e.getValue()
//            sb.append(if (value === this) "(this Map)" else value)
//            if (!i.hasNext()) {
//                return sb.append('}').toString()
//            }
//            sb.append(',').append(' ')
//        }
//    }
//
//    /**
//     * RadixTrieNode implements a radix array mapped trie node data structure.
//     *
//     *
//     *
//     * The radix is 32, and manage 5 bits of the int key.
//     *
//     *
//     *
//     * The prefix bits used to reach each node are stored in <tt>path</tt> variable.
//     * Each node stores all bits from parent nodes, and is not necessary to carry it
//     * traversing the trie.
//     *
//     *
//     *
//     * Each subtree of the RadixTrie can be cosidered a valid tree, because each
//     * subtree has all needed information needed to traverse and extract its
//     * information.
//     *
//     *
//     *
//     * To know the number of bits that forms the path,
//     * <tt>32 - the number of prefix used bits - 5</tt> is also stored.
//     *
//     *
//     *
//     * To save memory storing both values, and because the last five bits are never
//     * used in path, both values are combined in a single variable.
//     *
//     *
//     *
//     * Up to the highest 27 bits of path contain the prefix and the lowest 5
//     * contains the number of bits *not* used by the prefix.
//     *
//     *
//     *
//     * "number non prefix bits" term is used as synonymous of "number prefix bits"
//     * because initial resulted code operated always with its complement subtracting
//     * five. For performance, complement number of bits is used.
//     *
//     * <pre>
//     * `+----------------------------------+-------+
//     * | Prefix bits used in each node    | #bits |
//     * +----------------------------------+-------+
//     * | 00 00000 00000 00000 00000 00000 | 00000 |
//     * +----------------------------------+-------+
//     *
//    ` *
//    </pre> *
//     */
//    internal class RadixTrieNode(prefixBits: Int, numberNonPrefixBits: Int) :
//        Iterable<IntObjectEntry<*>> {
//        private var arr: Array<Any?>?
//        private var bitmap = 0
//        private val path: Int = prefixBits + numberNonPrefixBits
//
//        val numberNonPrefixBits: Int
//            /**
//             * Returns the number of bits that are not part of the path in this node
//             * NumberPrefixBits = 32 - NumberNonPrefixBits - 5
//             *
//             * @return the number of bits that are not used in the prefix stored in the node
//             */
//            get() = path and BIT_MASK
//
//        val isLeaf: Boolean
//            /**
//             * Returns true if the node is a leaf node
//             *
//             * @return true if the node is a leaf node
//             */
//            get() = (path and BIT_MASK) == 0
//
//        val prefixBits: Int
//            /**
//             * Returns prefix bits of the trie node
//             *
//             * @return prefix bits of the trie node
//             */
//            get() = path and MASK_PATH
//
//        /**
//         * Obtains the value associated to the trie node index
//         *
//         * @param idx
//         * index of the element in the uncompressed array
//         * @return the value associated
//         */
//        fun get(idx: Int): Any? {
//            if (isBitPresent(1 shl idx)) {
//                return arr!![getArrIdx(idx)]
//            }
//            return null
//        }
//
//        /**
//         * Stores a value in certain position. If an associated value already exists,
//         * overwrite it. If it doesn't exists, the compressed array increase the size in
//         * one element.
//         *
//         * @param idx
//         * index of the element in the uncompressed array
//         * @param value
//         * the value to store
//         * @return the previous value in <tt>idx</tt> position, or <tt>null</tt> if
//         * there was no value in <tt>idx</tt>.
//         */
//        fun set(idx: Int, value: V): Any? {
//            val bitIdx = 1 shl idx
//            if (isBitPresent(bitIdx)) {
//                val arrIdx = getArrIdx(idx)
//                val previousValue = arr!![arrIdx]
//                arr!![arrIdx] = value
//                return previousValue
//            }
//            bitmap = bitmap or bitIdx
//            if (arr == null) {
//                arr = kotlin.arrayOfNulls<Any>(1)
//                arr!![0] = value
//            } else {
//                val arrIdx = getArrIdx(idx)
//                val arrLen = arr!!.size
//                val arrIncreased = kotlin.arrayOfNulls<Any>(arrLen + 1)
//                if (arrIdx == arrLen) {
//                    arraycopy(arr, 0, arrIncreased, 0, arrLen)
//                } else if (arrIdx == 0) {
//                    arraycopy(arr, 0, arrIncreased, 1, arrLen - arrIdx)
//                } else {
//                    arraycopy(arr, 0, arrIncreased, 0, arrIdx)
//                    arraycopy(arr, arrIdx, arrIncreased, arrIdx + 1, arrLen - arrIdx)
//                }
//                arr = arrIncreased
//                arr!![arrIdx] = value
//            }
//            return null
//        }
//
//        /**
//         * Create a new node parent of the current node with two childs: the current
//         * node and a new leaf node with the given key and value.
//         *
//         * The parent node is created using 5 + number of lower shared bits by both
//         * childs nodes.
//         *
//         * @param key
//         * key with which the specified value is to be associated
//         * @param value
//         * value to be associated with the specified key
//         * @param numberNonPrefixBits
//         * number of non prefix bits used by both childs
//         * @return the created parent node with both childs
//         */
//        fun createParentNodeWith(key: Int, value: Any?, numberNonPrefixBits: Int): RadixTrieNode {
//            val parentNodePrefixBits = getKeyPrefixBits(key, numberNonPrefixBits + BIT_SIZE)
//            val parentNode = RadixTrieNode(parentNodePrefixBits, numberNonPrefixBits)
//            val idx1 = (path ushr numberNonPrefixBits) and BIT_MASK
//            val idx2 = (key ushr numberNonPrefixBits) and BIT_MASK
//            assert(idx1 != idx2)
//
//            val arr = kotlin.arrayOfNulls<Any>(2)
//            if (idx1 < idx2) {
//                arr[0] = this
//                arr[1] = newLeafNode(key, value)
//            } else {
//                arr[0] = newLeafNode(key, value)
//                arr[1] = this
//            }
//            parentNode.arr = arr
//            parentNode.bitmap = (1 shl idx1) + (1 shl idx2)
//            return parentNode
//        }
//
//        /**
//         * Removes the associated element in certain position and reduce the size of the
//         * compressed array if an element exists
//         *
//         * @param idx
//         * index of the element in the uncompressed array
//         * @return the previous value located in index value or <tt>null</tt> if there
//         * was no value associated to this possition
//         */
//        fun remove(idx: Int): Any? {
//            val bitIdx = 1 shl idx
//            if (!isBitPresent(bitIdx)) {
//                return null
//            }
//            val arrIdx = getArrIdx(idx)
//            val previousValue = arr!![arrIdx]
//            bitmap = bitmap and bitIdx.inv()
//            if (bitmap != 0) {
//                val arrLen = arr!!.size - 1
//                val arrDecreased = kotlin.arrayOfNulls<Any>(arrLen)
//                if (arrIdx == 0) {
//                    arraycopy(arr, 1, arrDecreased, 0, arrLen)
//                } else if (arrIdx == arrLen) {
//                    arraycopy(arr, 0, arrDecreased, 0, arrLen)
//                } else {
//                    arraycopy(arr, 0, arrDecreased, 0, arrIdx)
//                    arraycopy(arr, arrIdx + 1, arrDecreased, arrIdx, arrLen - arrIdx)
//                }
//                arr = arrDecreased
//            } else {
//                arr = null
//            }
//            return previousValue
//        }
//
//        val isEmpty: Boolean
//            /**
//             * Returns <tt>true</tt> if this array contains no elements.
//             *
//             * @return <tt>true</tt> if this array contains no elements
//             */
//            get() = bitmap == 0
//
//        /**
//         * Returns the number of elements stored in the node
//         *
//         * @return the number of elements stored in the node
//         */
//        fun size(): Int {
//            if (arr == null) {
//                return 0
//            }
//            return arr!!.size
//        }
//
//        /**
//         * Returns <tt>true</tt> if the <tt>bitIdx</tt> is set to 1. This means that a
//         * value is stored in the associated array.
//         *
//         * @param bitIdx
//         * possition in the bitmap
//         * @return <tt>true</tt> if the bit is 1
//         */
//        private fun isBitPresent(bitIdx: Int): Boolean {
//            return (bitmap and bitIdx) != 0
//        }
//
//        /**
//         * Returns the associated possition in the array of a bit from the bitmap. It
//         * takes the <tt>idx</tt> left bits in the bitmap and counts the number of
//         * present 1s.
//         *
//         * @param idx
//         * index in the bitmap
//         * @return the associated value in the compressed array
//         */
//        private fun getArrIdx(idx: Int): Int {
//            val mask = (-0x1 ushr (ARR_SIZE - 1 - idx))
//            return Integer.bitCount(mask and bitmap) - 1
//        }
//
//        fun forEach(action: IntObjectConsumer<Any?>) {
//            var it = 0
//            val highBits = this.prefixBits
//            var idx = 0
//            var mask = 1
//            while (idx < ARR_SIZE) {
//                if (isBitPresent(mask)) {
//                    action.accept(highBits + idx, arr!![it])
//                    it++
//                }
//                idx++
//                mask = mask shl 1
//            }
//        }
//
//        fun forEachKey(action: Consumer<Int>) {
//            val highBits = this.prefixBits
//            var idx = 0
//            var mask = 1
//            while (idx < ARR_SIZE) {
//                if (isBitPresent(mask)) {
//                    action.accept(highBits + idx)
//                }
//                idx++
//                mask = mask shl 1
//            }
//        }
//
//        fun forEachValue(action: Consumer<Any?>) {
//            var it = 0
//            var idx = 0
//            var mask = 1
//            while (idx < ARR_SIZE) {
//                if (isBitPresent(mask)) {
//                    action.accept(arr!![it])
//                    it++
//                }
//                idx++
//                mask = mask shl 1
//            }
//        }
//
//        override fun iterator(): Iterator<IntObjectEntry<*>?> {
//            if (arr == null) {
//                return emptyList<IntObjectEntry<*>?>()
//            }
//            return RadixTrieNode.ArrayIterator()
//        }
//
//        private inner class ArrayIterator : Iterator<IntObjectEntry<*>?> {
//            private var it = 0
//            private var idx = 0
//            private var mask = 1
//            private val highBits: Int = this.prefixBits
//
//            init {
//                gotoNext()
//            }
//
//            public override fun hasNext(): Boolean {
//                return it < arr!!.size
//            }
//
//            public override fun next(): IntObjectEntry<*> {
//                if (it >= arr!!.size) {
//                    throw NoSuchElementException()
//                }
//                val value: IntObjectEntry<*> = IntObjectEntry(highBits + idx, arr!![it++])
//                nextIndex()
//                gotoNext()
//                return value
//            }
//
//            fun gotoNext() {
//                while (idx < ARR_SIZE && !isBitPresent(mask)) {
//                    nextIndex()
//                }
//            }
//
//            fun nextIndex() {
//                idx++
//                mask = mask shl 1
//            }
//        }
//
//        override fun toString(): String {
//            if (this.isEmpty) {
//                return "{}"
//            }
//            val sb: StringBuilder = StringBuilder()
//            sb.append('{')
//            var first = true
//            if (this.isLeaf) {
//                val prefixBits = this.prefixBits
//                for (idx in 0..<ARR_SIZE) {
//                    val `object` = get(idx)
//                    if (`object` != null) {
//                        if (!first) {
//                            sb.append(", ")
//                        } else {
//                            first = false
//                        }
//                        sb.append(prefixBits + idx).append("=").append(`object`)
//                    }
//                }
//            } else {
//                for (idx in 0..<ARR_SIZE) {
//                    val `object` = get(idx)
//                    if (`object` != null) {
//                        if (!first) {
//                            sb.append(", ")
//                        } else {
//                            first = false
//                        }
//                        sb.append(`object`)
//                    }
//                }
//            }
//            sb.append('}')
//            return sb.toString()
//        }
//    }
//
//    companion object {
//        private const val BIT_SIZE = 5
//        private val ARR_SIZE = 1 shl BIT_SIZE
//        private val BIT_SHIFT = ARR_SIZE - BIT_SIZE
//        private val MASK_PATH = -0x1 shl BIT_SIZE
//        private val BIT_MASK = -0x1 ushr BIT_SHIFT
//
//        private val L1 = -0x1 shl BIT_SIZE * 2
//        private val L2 = -0x1 shl BIT_SIZE * 3
//        private val L3 = -0x1 shl BIT_SIZE * 4
//        private val L4 = -0x1 shl BIT_SIZE * 5
//        private val L5 = -0x1 shl BIT_SIZE * 6
//
//        private fun nonPrefixBitsSharedInXor(value: Int): Int {
//            if ((value and L1) == 0) {
//                return BIT_SIZE * 1
//            }
//            if ((value and L2) == 0) {
//                return BIT_SIZE * 2
//            }
//            if ((value and L3) == 0) {
//                return BIT_SIZE * 3
//            }
//            if ((value and L4) == 0) {
//                return BIT_SIZE * 4
//            }
//            if ((value and L5) == 0) {
//                return BIT_SIZE * 5
//            }
//            return 30
//        }
//
//        private fun getKeyPrefixBits(key: Int, numberNonPrefixBits: Int): Int {
//            if (numberNonPrefixBits < ARR_SIZE) {
//                return key and (-0x1 shl numberNonPrefixBits)
//            }
//            return 0
//        }
//
//        fun newLeafNode(key: Int, value: Any?): RadixTrieNode {
//            val node = RadixTrie.RadixTrieNode(key and MASK_PATH, 0)
//            node.bitmap = 1 shl (key and BIT_MASK)
//            node.arr = kotlin.arrayOfNulls<Any>(1)
//            node.arr!![0] = value
//            return node
//        }
//
//        private fun isLeafNode(numberNonPrefixBits: Int): Boolean {
//            return numberNonPrefixBits == BIT_SIZE
//        }
//
//        private fun getIdxInNode(key: Int, numberNonPrefixBits: Int): Int {
//            return (key ushr (numberNonPrefixBits - BIT_SIZE)) and BIT_MASK
//        }
//
//        private fun forEachKey(node: RadixTrieNode, action: Consumer<Int>) {
//            if (node.isLeaf) {
//                node.forEachKey(action)
//            } else {
//                node.forEach{ idx, value -> forEachKey((value as RadixTrie.RadixTrieNode?)!!, action) }
//            }
//        }
//
//        private fun containsValue(node: RadixTrieNode, value: Any?): Boolean {
//            if (node.isLeaf) {
//                for (e in node) {
//                    if (e.getValue().equals(value)) {
//                        return true
//                    }
//                }
//            } else {
//                for (e in node) {
//                    if (Companion.containsValue((e.getValue() as RadixTrie.RadixTrieNode?)!!, value)) {
//                        return true
//                    }
//                }
//            }
//            return false
//        }
//    }
//}